package com.berchen.数据结构.递归;

/**
 * 八皇后问题
 *
 * 8*8的棋盘上 每一行放一个棋子  保证任意两颗棋子不能在同一行 同一列 同一斜线
 */
public class EightQueen {

    private int size;
    private int[] arr;
    private int count;

    public int getCount() {
        return count;
    }

    public EightQueen(int size) {
        this.size = size;
        arr=new int[this.size];
    }

    /**
     * 下棋 从 棋盘开始下
     * @param n
     */
    public void chess(int n ){

        // 这一种解法已经出来了，就不要继续往下递归了
        if(n==size){
            count++;
            print();
            return;
        }
        // 从这一行的第一个棋盘开始遍历 直到遍历这一行结束
        for(int j=0;j<size;j++){
            arr[n]=j;
            if(isLegal(n)){
                // 合法 ，就开始遍历下一行
                chess(n+1);
            }
            // 不合法，就继续遍历该行下一个棋盘
        }
    }

    /**
     * 输出每一种解法
     */
    private void print(){
        for (int i =0;i<size;i++){
            System.out.printf("%d\t",arr[i]);
        }
        System.out.println();
    }

    /**
     * 判断第n个皇后现在这个位置是否合法
     * @param n
     * @return
     */
    private boolean isLegal(int n){

        // 遍历前面已经摆放了的棋子
        for(int i=0;i<n;i++){

            // arr[n]==arr[i] 判断是否在同一列
            // Math.abs(arr[n]-arr[i])==Math.abs(n-i) 判断是否在同一个斜线
            if(arr[n]==arr[i]||Math.abs(arr[n]-arr[i])==Math.abs(n-i)){
                return false;
            }
        }
        return true;
    }
}
